package main

import "go-leetcode/leetcode/utils"

func main() {
	lists := []*utils.ListNode{
		utils.GetListNodeByArray([]int{1, 4, 5}),
		utils.GetListNodeByArray([]int{1, 3, 4}),
		//utils.GetListNodeByArray([]int{2, 6}),
	}

	kLists := mergeKLists(lists)

	for kLists != nil {
		print(kLists.Val, "->")
		kLists = kLists.Next
	}

}

// mergeKLists 归并排序
func mergeKLists(lists []*utils.ListNode) *utils.ListNode {
	// 归并
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}

	listLen := len(lists)
	mid := listLen / 2

	leftList := lists[0:mid]
	rightList := lists[mid:]

	return MergeTwoLists(mergeKLists(leftList), mergeKLists(rightList))
}

// mergeKLists 简单顺序合并
func mergeKListsSimply(lists []*utils.ListNode) *utils.ListNode {
	var head *utils.ListNode

	for _, list := range lists {
		head = MergeTwoLists(head, list)
	}

	return head
}

func MergeTwoLists(list1 *utils.ListNode, list2 *utils.ListNode) *utils.ListNode {
	dummy := &utils.ListNode{
		Val:  -1,
		Next: nil,
	}
	prev := dummy
	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			prev.Next = list1
			list1 = list1.Next
		} else {
			prev.Next = list2
			list2 = list2.Next
		}
		prev = prev.Next
	}

	if list1 != nil {
		prev.Next = list1
	} else if list2 != nil {
		prev.Next = list2
	}

	return dummy.Next
}
